package org.example.myleet.p496;

public class Solution {
    /**
     * 思路：单调栈+哈希
     * 需要求下一个最大的数，利用单调栈单调特性，可以为递减或递增，这里使用递减特性，遇到递增的时候就重置栈
     * 哈希主要是快速找到目标值，由于题目给出范围，数字不可能大于10000，因此可以直接开数组存，否则可以用HashMap帮助
     * 复杂度O(nums1.length + nums2.length)
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //size和stack数组组成一个简陋的栈
        int size = 0;
        int[] stack = new int[nums2.length];
        //map作为nums1的元素哈希表，存储的值是对应数字的下一个更大的数
        int maxRange = 10001;
        int[] map = new int[maxRange];
        for (int i = 0; i < maxRange; ++i) {
            //初始化，全部-1
            map[i] = -1;
        }
        //初始化，nums2第一个数入栈
        stack[size++] = nums2[0];
        for (int i = 1; i < nums2.length; ++i) {
            //观察栈顶
            int top;
            while (size > 0 && nums2[i] > (top = stack[size - 1])) {
                //当栈顶小于nums2[i]，出现递增，破坏单调递减性时，不断弹出栈内元素，并记录弹出的元素的下一个更大值，直至恢复单调递减
                map[top] = nums2[i];
                --size;
            }
            //恢复单调递减，入栈
            stack[size++] = nums2[i];
        }
        //利用记录的哈希表直接得到结果
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            result[i] = map[nums1[i]];
        }
        return result;
    }
}
